#include "MaxHeap.h"
#include <stdlib.h>
#include <limits.h>
#include <stdio.h>

// 创建一个空的最大堆
MaxHeap *create(int maxSize) {
    MaxHeap *heap = malloc(sizeof *heap);
    heap->items = malloc(maxSize * sizeof(MaxHeapElemType));
    heap->size = 0;
    heap->capacity = maxSize;
    // 定义哨兵为int 最大值,便于以后更快操作
    heap->items[0] = INT_MAX;
    return heap;
}

// 判断最大堆是否已满
int isFull(MaxHeap *heap) {
    return heap->size == heap->capacity;
}

// 将元素插入到最大堆中
int insert(MaxHeap *heap, MaxHeapElemType item) {
    if (isFull(heap)) {
        printf("最大堆已满");
        return 0;
    }
    int i = ++heap->size;
    // 当item是比较根节点都还要大的时候，这个时候哨兵是int最大值，退出循环
    while (heap->items[i / 2] < item) {
        heap->items[i] = heap->items[i / 2];
        i /= 2;
    }
    heap->items[i] = item;
    return 1;
}

// 判断最大堆是为空
int isEmpty(MaxHeap *heap) {
    return heap->size == 0;
}

// 返回最大堆中最大的元素(高优先级)
MaxHeapElemType deleteMax(MaxHeap *heap) {
    if (isEmpty(heap)) {
        printf("最大堆为空");
        return INT_MAX;
    }
    MaxHeapElemType rootElemType = heap->items[1];
    // 要保证完全二叉树需要最后一个结点设置为根节点,并向下过滤调整为最大堆
    MaxHeapElemType temp = heap->items[heap->size--];
    int n = 1;
    while (n * 2 <= heap->size) {
        int i = n * 2;
        // 左右孩子最大值
        if (i != heap->size && heap->items[i] < heap->items[i + 1]) {
            i++;
        }
        if (temp < heap->items[i]) {
            heap->items[n] = heap->items[i];
        } else {
            break;
        }
        n = i;
    }
    heap->items[n] = temp;
    return rootElemType;
}

void maxHeapTest() {
    MaxHeap *maxHeap = create(8);
    insert(maxHeap, 57);
    insert(maxHeap, 32);
    insert(maxHeap, 16);
    insert(maxHeap, 25);
    insert(maxHeap, 88);
    insert(maxHeap, 69);
    insert(maxHeap, 64);
    insert(maxHeap, 10);

    printf("最大堆输出：\n");
    for (int i = 0; i < 8; ++i) {
        printf("i=%d ==> %d\n", i, deleteMax(maxHeap));
    }
}